package stacks

// 维护一个存储下标的单调栈
// 栈顶的下标对应的温度是最大值
// 遍历数组，如果栈为空，直接将i进栈，如果不为空，比较栈顶的下标对应的温度和当前温度的值
// 如果当前温度大于栈顶的对应的温度，将栈顶的prevIndex移除，同时将该prevIndex对应的天数赋值为 i - prevIndex
// 重复以上操作，只到栈为空，或者当前栈顶的温度小于当前的温度，将i进栈
func dailyTemperatures(temperatures []int) []int {
	ans := make([]int, len(temperatures))
	sk := []int{}
	for i := 0; i < len(temperatures); i++ {
		for len(sk) != 0 && temperatures[i] > temperatures[sk[len(sk) - 1]] {
			ans[sk[len(sk) - 1]] = i - sk[len(sk) - 1]
			sk = sk[:(len(sk) - 1)]
		}
		sk = append(sk, i)
	}
	return ans
}